The present invention relates to an apparatus that can quickly determine if multiple numbers are respectively contained in multiple numeric ranges. More particularly, the present invention relates to an apparatus that can quickly classify data packets transmitted over a digital communication network at high speeds by quickly determining if data values contained in the data packets are respectively contained in certain data ranges. Furthermore, the present invention relates to a method employed by the apparatus.
In many applications, classifying a group of numbers by determining whether or not the group of numbers falls within a specific group of numerical ranges is extremely useful. For example, in a digital communication network (e.g. the internet, wide area network (xe2x80x9cWANxe2x80x9d), local area network (xe2x80x9cLANxe2x80x9d), etc.), data packets are transmitted over the network between a source computer (e.g. a router, server, etc.) and a destination computer (e.g. a router, server, etc.). Each of the data packets typically includes a header that contains information identifying the type of data contained in the data packet, the source from which the data packet was transmitted, the intended destination of the data packet, etc.
FIG. 1 illustrates an example of a data packet header HDR that comprises a source internet protocol (xe2x80x9cIPxe2x80x9d) address field 2, a destination IP address field 4, a protocol field 6, a source port field 8, and a destination port field 10. The source IP address field 2 contains a 32-bit source IP address that identifies the computer transmitting the data packet. The destination IP address field 4 contains a 32-bit destination address that identifies the intended destination of the data packet. The protocol field 6 contains eight bits of protocol data that identify the data format and/or the transmission format of the data contained in the data packet. The source port field 8 includes 16 bits of data that identify the computer port that physically outputs the data packet, and the destination port field 10 contains 16 bits of data that represent the computer port that is supposed to input the data packet.
When data packets are transmitted over the network from the source computer to the destination computer, they are input by various routers, firewalls, and other network components. Such components may be included in the destination computer and/or may be contained in an intermediate computer that processes the data as it is being transmitted from the source computer to the destination computer. Before processing the data packet, a network component must xe2x80x9cclassifyxe2x80x9d the data packet according to various characteristics of the data packet and/or the data contained in the packet. Then, the network component processes the data packet based on its classification.
A data packet is usually classified by evaluating the information contained in the data packet header. For example, if the data packet contains the header HDR shown in FIG. 1, a network component may classify the data packet as a first type of data packet if the source IP address falls within a first range of source IP addresses, the destination IP address falls within a first range of destination IP addresses, the protocol data falls within a first range of protocol data values, the source port data falls within a first range of source port data values, and the destination port data falls within a first range of destination port data values. On the other hand, the internet component may classify the data packet as a second type of data packet if the source IP address, destination IP address, protocol data, source port data, and destination port data respectively fall within a second range of source IP addresses, a second range of destination IP addresses, a second range of protocol data values, a second range of source port data values, and a second range of destination port data values. Each group of data value ranges by which a data packet is classified may be considered to be a xe2x80x9crulexe2x80x9d. Thus, in the example above, the data packet is classified as a first type of data packet if it satisfies a first rule and is classified as a second type of data packet if it satisfies a second rule.
After the data packet is classified, the network component is able to determine how handle or process the data. For instance, based on the classification of the data packet, the network component may output the data packet via a particular transmission path so that it quickly reaches the intended destination computer, may determine that the data packet is authorized to be received and further processed by the internet component, may prevent the packet from being forwarded on the network, may process the data contained in the data packet in a particular manner, etc. Accordingly, the network component acts as a filter that classifies incoming data packets according to various rules based on the specific data values contained in the data packet headers and then processes the data packets based on their classification.
Since the network component must classify each and every data packet that it receives, it should ideally classify the data packets at a speed that equals at least the speed at which the data packets are received. By classifying the data packets as quickly as they are received, data packets do not become xe2x80x9cbottleneckedxe2x80x9d at the input of the internet component, and the overall operational speed of the network is not degraded.
Currently, high speed Sonet and Ethernet networks are capable of transmitting data at speeds of one gigabit per second and are widely implemented in LANs and WANs. Furthermore, fiber optic networks capable of transmitting data at speeds of ten gigabits per second are expected to be developed soon. Moreover, interconnects that can transmit data at 40 gigabits per second are currently being tested and will additionally increase the overall speed at which data travels over the LANs and WANs. In light of the present and foreseeable transmission speeds of data networks, network components must be able to classify and filter data packets at extraordinary speeds. For example, on a high speed Sonet network that is capable of transmitting ten gigabits per second, data packets can be transmitted at a rate of 30 million packets per second, and on a full duplex line, data packets can be transmitted at about 60 million packets per second.
As described above, network components classify each incoming data packet by evaluating its header and selecting a rule from among multiple rules that corresponds to the data in the header. Furthermore, a typical component uses hundreds of rules to classify data packets. Thus, in order to properly classify the incoming data packets without creating a bottleneck at the input of the network component, the component must determine which rule of the hundreds of rules corresponds to each of the incoming data packets and must make such determination at a very high speed. Furthermore, as the number of network users and the number of different services available on the network increase, the number of rules that will need to be evaluated by standard network components is expected to grow to ten thousand or more in the near future. As a result, the network components will need to classify data packets according to an extremely large number of rules at incredible speeds.
One proposal for designing network components to classify data packets is to combine dedicated hardware and conventional central processing units (xe2x80x9cCPUsxe2x80x9d). However, such a design requires hundreds of CPUs that are each capable of executing more than one billion instructions per second. Furthermore, as the number of rules that need to be evaluated and the speed at which the rules must be evaluated increase, designing a network component in the proposed manner will be impractical because the speed of the CPUs will be too slow and the overall cost of the network component will become extremely expensive.
Also, some network components suggest using a combination of dedicated hardware and processing elements, such as the components described in the following article: Stiliadis, D. xe2x80x9cHigh-Speed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matchingxe2x80x9d ACM SIGCOMM 1998 published in February 1998. The processing elements disclosed in the article are fairly simple and can basically be implemented with a comparator and a state machine. However, each field of the data packet header requires its own processing element, and a particular device disclosed in the article evaluates data packet headers having five fields and comprises five 128 Mbit synchronous static random access memories (xe2x80x9cSRAMsxe2x80x9d) and one field programmable gate array (xe2x80x9cFPGAxe2x80x9d). The particular device is able to classify data packets based on up to 512 rules and is able to process one million packets per second in a worst case scenario.
However, the device disclosed in the article above has many disadvantages. For example, the amount of memory required by the device increases exponentially as the number of rules to be evaluated increases. In addition, the number of times that the memory of the device must be accessed increases linearly as number of rules increases. Therefore, in practical operations, the disclosed device is only capable of evaluating approximately 1,000 rules for data packets having headers with five fields or less.
The use of content addressable memories (xe2x80x9cCAMsxe2x80x9d) for detecting if one or more data values equal one or more predetermined values is well known. Such memories have been used in memory management systems for converting virtual addresses to physical addresses. In addition, U.S. Pat. No. 5,745,488 (invented by Thompson et al.) discloses evaluating a data packet by using a CAM and is incorporated herein by reference for all purposes. However, in the above patent, the CAM can only compares the data values contained in the packet with individual data values and cannot compare the data values with ranges of values. Thus, the CAM cannot be used in many advanced network components that require sophisticated classification of data packets based on predetermined ranges of values. Since the classification capabilities of the CAM is limited, the CAM cannot practically classify a data packet by evaluating a header having more than five fields and by comparing the header to more than 1,000 rules.
One object of the present invention is to provide an apparatus that can quickly and accurately classify data packets according to a large number of rules.
Another object of the present invention is to provide an apparatus that can quickly classify data packets without using a processor that executes time consuming processing routines.
Yet another object of the present invention is to provide an apparatus in which the time required to classify data packets does not substantially increase as the number of rules used to classify the data packets increases.
In order to achieve the above and other objects, a device for classifying input data is provided and comprises: a first memory unit that stores a first maximum data value and a first minimum data value, wherein said first maximum data value and said first minimum data value define a first data range; and a first comparison circuit that inputs first data, said first minimum data value, and said first maximum data and determines a first relationship between said first data and said first data range, wherein said first comparison circuit outputs a first comparison signal based on said first relationship, wherein said first data corresponds to at least a first portion of said input data, and wherein said first comparison signal corresponds to a classification of said input data.
In order to further achieve the above and other objects, a classification device for classifying input data comprising first data and second data is provided. The classification device comprises: a first memory unit that stores a first maximum data value and a first minimum data value, wherein said first maximum data value and said first minimum data value define a first data range; a second memory unit that stores a second maximum data value and a second minimum data value, wherein said second maximum data value and said second minimum data value define a second data range; a first comparison circuit that inputs said first data, said first minimum data value, and said first maximum data value, determines whether or not said first data and said first data range have a first predetermined relationship, and outputs a corresponding first comparison signal; a second comparison circuit that inputs said second data, said second minimum data value, and said second maximum data value and determines whether or not said second data and said second data range have a second predetermined relationship, wherein said second comparison circuit outputs a second comparison signal when said second data and said second data range have said second predetermined relationship; and a first hit line, wherein said first hit line is coupled to said first comparison circuit and said second comparison circuit and is forced to a first logical value when said first comparison signal indicates that said first predetermined relationship is not satisfied or said second comparison signal indicates that said second predetermined relationship is not satisfied, wherein said first memory unit, said second memory unit, said first comparison circuit, said second comparison circuit, and said first hit line define a first cell of said classification device, wherein said first predetermined relationship and said second predetermined relationship define a first classification rule of said first cell, and wherein said classification device does not classify said input data according to said first classification rule when said first hit line has said first logical value and classifies said input data according to said first classification rule when said first hit line has a second logical value.
In order to even further achieve the above and other objects, a classifying device for receiving input data that comprises first data and second data and for classifying said input data based on the values of said first data and said second data is provided. The classifying device comprises: a content addressable memory that comprises a first row and a second row, wherein said first row includes: a first memory unit that stores a first minimum value and a first maximum value defining a first range; a first compare circuit coupled to said first memory unit; a second memory unit that stores a second minimum value and a second maximum value defining a second range; and a second compare circuit coupled to said second memory unit, wherein said second row includes: a third memory unit that stores a third minimum value and a third maximum value defining a third range; a third compare circuit coupled to said third memory unit; a fourth memory unit that stores a fourth minimum value and a fourth maximum value defining a fourth range; and a fourth compare circuit coupled to said fourth memory unit, wherein said first compare circuit inputs said first maximum and minimum values and said first data and determines whether or not said first data and said first range have a first relationship, wherein said second compare circuit inputs said second maximum and minimum values and said second data and determines whether or not said second data and said second range have a second relationship, wherein said third compare circuit inputs said third maximum and minimum values and said first data and determines whether or not said first data and said third range have a third relationship, and wherein said fourth compare circuit inputs said fourth maximum and minimum values and said second data and determines whether or not said second data and said fourth range have a fourth relationship.